//https://leetcode.cn/problems/letter-combinations-of-a-phone-number/submissions/

#include <iostream>
#include <vector>
#include <string>
using namespace std;

class Solution
{
    string _num_to_str[10] = { "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };
public:
    void combine_re(string& digits, int depth, string combine_str, vector<string>& vec_str)
    {
        if (digits[depth] == 0)
        {
            vec_str.push_back(combine_str);
            return;
        }

        string str(_num_to_str[digits[depth] - '0']);
        //str = _num_to_str[digits[depth] - '0'];
        for (auto c : str)
        {
            combine_re(digits, depth + 1, combine_str + c, vec_str);
        }
    }

    vector<string> letterCombinations(string digits)
    {
        vector<string> vec_str;
        if (digits.size() == 0)
            return vec_str;
        combine_re(digits, 0, "", vec_str);
        return vec_str;
    }
};

int main()
{
    Solution s;
    vector<string> ret = s.letterCombinations("23");
    return 0;
}